package com.tucc.hello.leetcode.no1_400.no1_200.no81_100.no95;

import com.tucc.hello.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution2 {

    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        List<TreeNode> treeNodeList = solution.generateTrees(4);
        treeNodeList.forEach(root -> {
            TreeNode.printPreOrder(root);
            System.out.println();
        });
    }

    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> treeNodeList = new ArrayList<>();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        generateTrees(nums, n, treeNodeList);
        return treeNodeList;
    }

    private void generateTrees(int[] nums, int size, List<TreeNode> treeNodeList) {

        for (int i = 0; i < size; i++) {
            swap(nums, i, size - 1);
            generateTrees(nums, size - 1, treeNodeList);
            swap(nums, i, size - 1);
        }

        if (size == 0) {
            TreeNode root = null;
            for (int i = 0; i < nums.length; i++) {
                root = addTreeNode(root, nums[i]);
            }
            if (root != null) {
                treeNodeList.add(root);
            }
        }
    }

    private TreeNode copyTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode copy = new TreeNode(root.val);
        copy.left = copyTree(root.left);
        copy.right = copyTree(root.right);
        return copy;
    }

    private void swap(int[] nums, int a, int b) {
        if (a != b) {
            int temp = nums[a];
            nums[a] = nums[b];
            nums[b] = temp;
        }
    }


    private TreeNode addTreeNode(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
        } else if (root.val >= val) {
            root.left = addTreeNode(root.left, val);
        } else {
            root.right = addTreeNode(root.right, val);
        }
        return root;
    }

}
